COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00010 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A01.Tex[154,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, October 4, 1989}
\leftline{\sevenrm Unpublished draft}
\noindent {\bf Not All Languages are FMLs}

There are languages for which no finite machine is a recognizer. There are
several proofs. The first is called a diagonal proof, after the style
of the following classical proof that there are irrational numbers.

Imagine writing in a column all the rational numbers between 0 and~1 in
a systematic order, with their decimal expansions beside them.
$$\baselineskip 18pt\vcenter{\halign{$#$\hfil\qquad&$#$\hfil\cr
1/2&0.\;{\underline 5}\;0\;0\;0\;0\;0\;0\cr
1/3&0.\;3\;{\underline 3}\;3\;3\;3\;3\;3\cr
2/3&0.\;6\;6\;{\underline 6}\;6\;6\;6\;6\cr
1/4&0.\;2\;5\;0\;{\underline 0}\;0\;0\;0\cr
2/4&0.\;5\;0\;0\;0\;{\underline 0}\;0\;0\cr
3/4&0.\;7\;5\;0\;0\;0\;{\underline 0}\;0\cr
1/5&0.\;2\;0\;0\;0\;0\;0\;{\underline 0}\cr
2/5&0.\;4\;0\;0\;0\;0\;0\;0\;{\underline 0}\cr
3/5&0.\;6\;0\;0\;0\;0\;0\;0\;0\;{\underline 0}\cr
4/5&0.\;8\;0\;0\;0\;0\;0\;0\;0\;0\;{\underline 0}\cr
1/6&0.\;1\;6\;6\;6\;6\;6\;6\;6\;6\;6\;{\underline 6}\;\ldots\cr
2/6&0.\;3\;3\;3\;3\;3\;3\;3\;3\;3\;3\;3\;{\underline 3}\;\ldots\cr
3/6&0.\;5\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;0\;{\underline 0}\cr}}$$
Reading down the underlined digits on the diagonal, 
we find another number,
$0.5360000000630\ldots\,$. Change all of its digits to~0, except that
zeroes are changed to ones; it becomes $0.0001111111001\ldots\,$.
This number is different in at least one digit from any rational number;
for example, it is different from $3/5$ in the ninth decimal place
because of the way it was constructed. In fact, the diagonal proof
shows that any infinite sequence of real numbers omits some real number.

The analogous proof about languages shows that no technique for naming
a class of languages includes all languages, or even all languages
in $\{0,1\}↑{\ast}$. Write down in a column all the names of languages,
and in a second column encode these names in binary:
$$\vcenter{\halign{$#$\hfil\qquad&#\hfil\cr
\emptyset&110\cr
\epsilon&111\cr
0&000\cr
1&001\cr
0↑{\ast}∪1&000 011 010 001\cr
(0∪11)↑{\ast}1&100 000 010 001 001 101 011 001\cr
(0∪1)↑{\ast}&100 000 010 001 101 011\cr
\quad\vdots\cr}}$$
$$\vcenter{\halign{#\hfil\quad&$#$\hfil\qquad&#\hfil\cr
code:&0&000\cr
&1&001\cr
&∪&010\cr
&\ast&011\cr
&(&100\cr
&)&101\cr
&\emptyset&110\cr
&\epsilon&111\cr}}$$
Notice that the code for language $(0∪1)↑{\ast}$ belongs to that language;
none of the other codes happen to belong to the language they name.

{\narrower\smallskip\noindent
{\bf Drill:} What about the codes for $(0∪1)↑{\ast}1$, \dots ?\smallskip}

Let language $L$ contain a code $c$ iff $c$ is a code for a regular expression
$e$, and $c$ does {\it not} belong to the language $e$ names.
For example, $L$~includes 000
but not 100 000 010 001 101 011.
We will prove $L$~is not a~FML. If $L$~were, it would have a regular
expression~$e$ naming $L$, and $e$~would have a code~$c$ naming~$L$. 
Two possibilities arise:

\disleft 25pt:
(1):$c\in L$. Then $c$ belongs to the language $e$ names, and by definition
of~$L$, $c\notin L$, contradiction.

\disleft 25pt:
(2):$c\notin L$. Then $c$ does not belong to the language $e$ names, and by
definition of~$L$, $c\in L$, contradiction.

\noindent
So, assuming $L$ to be a FML leads to contradiction; no finite machine
recognizes~$L$. We shall later have the tools to show that some non-finite
machines can recognize~$L$.

A second proof that there are languages that are not FMLs is simpler, but
does not generalize to so many other kinds of languages. Let
$L=\{0↑i1↑i,i≥0\}$; that is, $L=\{\epsilon,01,0011,000111,\hbox{ etc.}\}$.
Suppose there were a DFM for~$L$. Let it read zeroes until it goes through
some state~$q$ twice, say after reading~$j$ zeroes and after $k$~zeroes,
$0≤j<k$. Now start the machine again letting it read $j$~zeroes to reach
state~$q$, and then $j$~ones to reach state $q'\in F$. Start it one more
time, letting it read $k$~zeroes to reach~$q$, and $j$~ones to reach
$q'\in F$. So it accepts $0↑k1↑j$, contrary to the definition of~$L$.
The key fact about the machine we used is that, being finite, it must
repeat a state. This proof is a particular application of the {\sl pumping
theorem\/}, soon to be shown, the most powerful tool for showing that 
particular languages are not FMLs.

\bye